/*
Sort List Total Accepted: 45914 Total Submissions: 208683 My Submissions Question Solution
Sort a linked list in O(n log n) time using constant space complexity.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


class Solution {
public:
	ListNode *getMidNode(ListNode* head)
	{
		ListNode *fast = head->next;
		ListNode *slow = head->next;
		ListNode *prev = head;

		while (fast!=NULL)
		{
			if (fast != NULL)
				fast = fast->next;
			
			if (fast!=NULL)
			{
				fast = fast->next;
			}
			else
			{
				break;
			}
			prev = slow;
			slow = slow->next;

		}
		prev->next = NULL;
		return slow;
	}
	ListNode* merge(ListNode* head1, ListNode* head2)
	{
		ListNode *newHead = new ListNode(-1);
		ListNode *newTail = newHead;

		while (head1!=NULL && head2!=NULL)
		{
			if (head1->val <= head2->val)
			{
				newTail->next = head1;
				head1 = head1->next;
			}
			else
			{
				newTail->next = head2;
				head2 = head2->next;
			}
			newTail = newTail->next;
			newTail->next = NULL;


		}

		if (head1!=NULL)
		{
			newTail->next = head1;
		}
		if (head2!=NULL)
		{
			newTail->next = head2;

		}
	
		return newHead->next;
	}
	ListNode* sortList(ListNode* head) {
		if (head == NULL||head->next==NULL)
		{
			return head;
		}

		ListNode* head1 = head;
		ListNode* head2 = getMidNode(head);
		head1 = sortList(head1);
		head2 = sortList(head2);
		return merge(head1,head2);


	}
};
int main(int argc, char* argv[])
{

	ListNode *head = new ListNode(1);
	ListNode *head1 = new ListNode(3);
	ListNode *head2 = new ListNode(2);
	ListNode *head3 = new ListNode(5);
	ListNode *head4 = new ListNode(4);

	head->next = head1;
	head1->next = head2;
	head2->next = head3;
	head3->next = head4;
	Solution s;
	head = s.sortList(head);

	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;